package bintree.leetcode;

import java.util.*;

/**
 * @Author: yuisama
 * @Date: 2021/9/4 12:58
 * @Description:二叉树层序遍历
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 */
public class Num102_LevelOrder {
    List<List<Integer>> res = new ArrayList<>();
    // BFS递归写法，类似链表遍历，将二叉树的每一层当做链表的一个节点
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return res;
        }
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        traverse(nodes);
        return res;
    }

    private void traverse(List<TreeNode> curListNodes) {
        // base case,当前列表为空，表示当前层已经遍历结束,走到叶子节点
        if (curListNodes.isEmpty()) {
            return;
        }
        // 前序位置，当前层每个节点的值
        List<Integer> curListVal = new ArrayList<>();
        // 下一层每个节点
        List<TreeNode> nextList = new ArrayList<>();
        for (TreeNode node : curListNodes) {
            curListVal.add(node.val);
            if (node.left != null) {
                nextList.add(node.left);
            }
            if (node.right != null) {
                nextList.add(node.right);
            }
        }
        res.add(curListVal);
        // 继续遍历下一层
        traverse(nextList);
        // 后序位置添加再添加当前层节点值，可以得到自底向上的结果集
        // res.add(curListVal);
    }
//    // DFS递归法一.前序遍历的思路
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        if (root == null) {
//            return res;
//        }
//        // 根节点为第一层
//        traverse(root,0);
//        return res;
//    }
//
//    /**
//     * DFS遍历树的每层节点
//     * @param root
//     * @param depth
//     */
//    private void traverse(TreeNode root, int depth) {
//        if (root == null) {
//            return;
//        }
//        // 前序位置
//        if (res.size() <= depth) {
//            // 第一次走到该层节点，创建新的列表
//            res.add(new LinkedList<>());
//        }
//        // 添加当前节点到结果集
//        res.get(depth).add(root.val);
//        traverse(root.left,depth + 1);
//        traverse(root.right,depth + 1);
//    }
    // BFS迭代法
//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> retList = new ArrayList<>();
//        if (root == null) {
//            return retList;
//        }
//        Queue<TreeNode> queue = new ArrayDeque<>();
//        queue.offer(root);
//        while (!queue.isEmpty()) {
//            // 当前队列就是当前所处层级的节点
//            int size = queue.size();
//            List<Integer> level = new ArrayList<>();
//            for (int i = 0; i < size; i++) {
//                TreeNode node = queue.poll();
//                level.add(node.val);
//                // 存储下一层的节点
//                if (node.left != null) {
//                    queue.offer(node.left);
//                }
//                if (node.right != null) {
//                    queue.offer(node.right);
//                }
//            }
//            retList.add(level);
//        }
//        return retList;
//    }
}
